/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* reverseList(ListNode* head) 
    {
        ListNode* newHead = nullptr; // 新链表的头指针，初始为空
        ListNode* cur = head; // 当前节点指针，从头节点开始
        while(cur) 
        {
            ListNode* curNext = cur->next; // 保存当前节点的下一个节点
            cur->next = newHead; // 将当前节点插入到新链表的头部
            newHead = cur; // 更新新链表的头指针
            cur = curNext; // 移动到下一个节点
        }
        return newHead; // 返回反转后的链表头
    }
    
    ListNode* middleNode(ListNode* head) 
    {
        ListNode* fast = head; // 快指针，每次移动两步
        ListNode* slow = head; // 慢指针，每次移动一步
        while(fast != nullptr && fast->next != nullptr) 
        {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow; // 慢指针指向的就是中间节点
    }
    
    bool isPalindrome(ListNode* head)
    {
        ListNode* mid = middleNode(head); // 找到链表的中间节点
        ListNode* reverse_mid = reverseList(mid); // 反转后半部分链表
        while(head && reverse_mid) 
        {
            if(head->val != reverse_mid->val) // 比较前后两部分节点的值
            {
                return false; // 如果不相等，不是回文链表
            }
            else 
            {
                head = head->next; // 前半部分指针后移
                reverse_mid = reverse_mid->next; // 后半部分指针后移
            }
        }
        return true; // 所有节点都匹配，是回文链表
    }
};